/*
 * @Author: liusheng
 * @Date: 2022-04-10 12:42:14
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-10 13:55:58
 * @Description: 
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 
 * 
 剑指 Offer II 019. 最多删除一个字符得到回文
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

 

示例 1:

输入: s = "aba"
输出: true
示例 2:

输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符
示例 3:

输入: s = "abc"
输出: false
 

提示:

1 <= s.length <= 105
s 由小写英文字母组成
 

注意：本题与主站 680 题相同： https://leetcode-cn.com/problems/valid-palindrome-ii/
 */
#include <string>
using namespace std;

class Solution_Wrong {
public:
    bool validPalindrome(string s) {
        int n = s.size();
        if (n < 2)
        {
            return true;
        }

        int left = 0;
        int right = n - 1;
        bool hasDeleted = false;
        while (left < right)
        {
            if (s[left] != s[right])
            {
                if (hasDeleted)
                {
                    return false;
                }
                /*
                in else: the left + 1 and right - 1 check is not correct for the below test case:
                reason:left + 1 may equal to right,but can not ensure the following string after delete left is a Palindrome
                may right - 1 also make sense,but left will continue;
                aguokepatgbnvfqmgml cupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuc u lmgmqfvnbgtapekouga
                */
                else
                {     
                    if (left + 1 < right && s[left + 1] == s[right])
                    {
                        ++left;
                        hasDeleted = true;
                        continue;
                    }
                    if (right - 1 > left)
                    {
                        --right;
                        hasDeleted = true;
                        continue;
                    }
                    return false;
                }
            }
            ++left;
            --right;
        }

        return true;
    }
};

class Solution {
public:
    bool validPalindrome(string s) 
    {
        int n = s.size();
        if (n < 2)
        {
            return true;
        }

        int left = 0;
        int right = n - 1;
        while (left < right)
        {
            if (s[left] != s[right])
            {
                //check if delete left character or delete right character can be validPalindrome
                return validPalindrome(s,left + 1,right) || validPalindrome(s,left,right - 1);
            }
            ++left;
            --right;
        }

        return true;
    }
    
private:
    bool validPalindrome(string & s,int left,int right)
    {
        bool result = true;
        while (left < right)
        {
            if (s[left++] != s[right--])
            {
                return false;
            }
        }

        return true;
    }
};
